#include "SearchTree.h"
#include <stdio.h>
#include <stdlib.h>
#include "Queue1.h"

struct _treeNode {
    ElementType2 data;
    struct _treeNode *left, *right;
};

//测试函数
void TestSearchTree() {
    SearchTree t1 = NULL;
    int ii;
    for (int i = 0; i < 20; i++) {
        srand(i);
        int temp = rand() % 100;
        t1 = Insert(t1, temp);
        printf("%d\t", temp);
        ii = temp;
    }
    printf("\nPreOrder:\n");
    PreOrder(t1, Display2);
    printf("\nInOrder:\n");
    InOrder(t1, Display2);
    printf("\nPostOrder:\n");
    PostOrder(t1, Display2);
    printf("\nLevelOrder:\n");
    LevelOrder(t1, Display2);
    printf("\nMin=%d\n", FindMin(t1)->data);
    printf("\nMax=%d\n", FindMax(t1)->data);
    printf("\nii=%d,Find(ii)=%d\n", ii, Find(t1, ii)->data);
    printf("After deleting:\n");
    t1 = DeleteEle(t1, 46);
    LevelOrder(t1, Display2);

    DisposeSearchTree(t1);
}

//插入新元素,相同元素不重复添加
//此为重难点位置
SearchTree Insert(SearchTree tree, ElementType2 data) {
    if (tree) {
        //如果根节点非NULL
        if (data < tree->data) {
            tree->left = Insert(tree->left, data);
        }
        if (data > tree->data) {
            tree->right = Insert(tree->right, data);
        }
    } else {
        //如果根节点为NULl
        tree = (TreeNode*)malloc(sizeof(TreeNode));
        tree->data = data;
        tree->left = NULL;
        tree->right = NULL;
    }

    return tree;
}

//销毁
void DisposeSearchTree(SearchTree tree) {
    Empty(tree);
}

//查找最大值
TreeNode* FindMax(SearchTree tree) {
    if (tree) {
        TreeNode* temp = tree;
        TreeNode* res = NULL;
        while (temp) {
            res = temp;
            temp = temp->right;
        }
        return res;
    }
    return NULL;
}

//查找最小值
TreeNode* FindMin(SearchTree tree) {
    if (tree) {
        TreeNode* temp = tree;
        TreeNode* res = NULL;
        while (temp) {
            res = temp;
            temp = temp->left;
        }
        return res;
    }
    return NULL;
}

//查找指定值
TreeNode* Find(SearchTree tree, ElementType2 data) {
    if (tree) {
        if (data < tree->data)
            return Find(tree->left, data);
        else if (data > tree->data)
            return Find(tree->right, data);
        else
            return tree;
    }
    return NULL;
}

//删除元素
SearchTree DeleteEle(SearchTree tree, ElementType2 data) {
    //二叉树为空，返回
    if (!tree)
        return NULL;

    if (data < tree->data) {
        tree->left = DeleteEle(tree->left, data);
        return tree;
    } else if (data > tree->data) {
        tree->right = DeleteEle(tree->right, data);
        return tree;
    } else {
        //找到该节点,有两子节点
        if (tree->left && tree->right) {
            TreeNode* temp = FindMin(tree->right);
            tree->data = temp->data;
            tree->right = DeleteEle(tree->right, temp->data);
            return tree;
        }
        //叶子结点
        else if (!tree->left && !tree->right) {
            return NULL;
        }
        //有一个子节点
        else {
            TreeNode* res = tree->left ? tree->left : tree->right;
            free(tree);
            return res;
        }
    }
}

//清空元素
void Empty(SearchTree tree) {
    if (tree) {
        Empty(tree->left);
        Empty(tree->right);
        free(tree);
    }
}

//四种遍历方式,递归方法实现非常简单，层序遍历有技巧
//注意：应该判断NULL情况，任何时候都应该关注这个问题！！！
void PreOrder(SearchTree tree, DisplayFunc display) {
    if (tree) {
        display(tree->data);
        if (tree->left)
            PreOrder(tree->left, display);
        if (tree->right)
            PreOrder(tree->right, display);
    }
}

void InOrder(SearchTree tree, DisplayFunc display) {
    if (tree) {
        InOrder(tree->left, display);
        display(tree->data);
        InOrder(tree->right, display);
    }
}

void PostOrder(SearchTree tree, DisplayFunc display) {
    if (tree) {
        PostOrder(tree->left, display);
        PostOrder(tree->right, display);
        display(tree->data);
    }
}

void LevelOrder(SearchTree tree, DisplayFunc display) {
    if (tree) {
        Queue* q = CreateQueue();

        EnQueue(q, tree);
        while (!IsEmpty(q)) {
            TreeNode* temp = DeQueue(q);
            display(temp->data);
            if (temp->left)
                EnQueue(q, temp->left);
            if (temp->right)
                EnQueue(q, temp->right);
        }

        DisposeQueue(q);
    }
}

void Display2(ElementType2 data) {
    printf("%d\t", data);
}